Various software tools for three-dimensional modeling are used today, including computer-aided design (CAD) systems that help draftsmen create drawings. CAD software runs on a computer, permitting the user to draft a three-dimensional structure on a display screen by entering values and commands and manipulating graphical objects using input devices. Viewing pictures on the screen, the user creates a drawing while keeping the structure's solid image in his or her mind.
Three-dimensional coordinate data of a solid object is used to represent its spatial shape in a computer. For example, the Standard Triangulated Language (STL) is a data format for describing three-dimensional shapes. STL format uses a set of triangles to express the shape of a three-dimensional model. To describe each such triangle, STL data includes the coordinates of its three vertices (corners) and a normal vector of its triangular plane.
CAD users may sometimes need to search for existing three-dimensional models in relation to a specific model. For example, an engineer engaged in designing a component of a product may wish to ensure that he or she is not reinventing the wheel (i.e., creating a mere duplicate of an existing component design), which is best avoided. The engineer uses a conventional similarity search method to retrieve existing three-dimensional models that resemble a specified model in shape. For example, one such method quantifies geometric features of each three-dimensional model. The resulting value is referred to as a characteristic quantity. When two models have similar characteristic quantities, they are supposed to be similar in shape. It is also possible to calculate a plurality of characteristic quantities in several different aspects of a single three-dimensional model. These characteristic quantities form a characteristic vector for use in a similarity search of models.
For example, characteristic quantities of a model may be obtained as a distribution of distances between the center of mass and faces of the model. Another proposed method uses the average of crease angles each formed by the normal vectors of two adjacent faces. Yet another proposed method produces nodes of an analytical tree by mapping patches constituting a three-dimensional model to them and generates a neighborhood graph by placing an edge to each pair of geometrically adjacent nodes. The trees produced in this way are used to detect differences in shape between two or more models. Still another proposed method reduces a complex three-dimensional model into a simplified model called “skeleton.” Some significant features are then extracted from the model and its skeleton, and the resulting characteristic vector is registered in a database. See, for example, the following documents:
Japanese Laid-open Patent Publication No. 2000-222428
Japanese Laid-open Patent Publication No. 2001-307111
Japanese National Publication of International Patent Application No. 2006-520948
As noted above, a three-dimensional structure may be expressed as a set of polygons (e.g., STL data is a collection of triangles), where each vertex of the structure corresponds to a vertex of a polygon, and each edge between two vertices of the structure corresponds to a shared edge of polygons. Structure data may be formed into a graph by mapping the structure's vertices and edges to graph nodes and edges, and characteristic quantities calculated from such graph data are used to seek similar shapes. This graph data, however, lacks the information about angles formed by polygon edges of a structure, thus making it difficult to reflect the structure's convex or concave features in the characteristic quantities. It is indeed not realistic to include every edge-to-edge angle in graph data because of its consequent increase in data size.